package com.atwy.graph.undirectedgraph;

/**
 * @Author: 30467
 * @Date: 2022/3/8
 * DFS:深度搜索
 * 用递归方法遍历所有顶点，在访问一个顶点时：
 * 1.将它标记为已访问；
 * 2.递归地访问它的所有没有被标记过的邻居顶点。
 * <p>
 * 单点路径：给定一幅图和一个起点s，从s到给定目的的顶点v是否存在一条路径，如果有，找出这条路径。
 */
public class DepthFirstSearch {
    /**
     * 这个顶点上调用过dfs()了吗？
     */
    private boolean[] marked;
    private int count;
    /**
     * 从起点到一个顶点的已知路径上的最后一个顶点
     * 是一棵父链接表示的树
     * edgeTo[w]=v,表示 v 是 w 的前驱节点
     */
    private int[] edgeTo;
    /**
     * 起点
     */
    private int s;

    /**
     * 构建邻接矩阵的深度优先搜索
     *
     * @param graph
     * @param s
     */
    public DepthFirstSearch(IGraph graph, int s) {
        marked = new boolean[graph.V()];
        edgeTo = new int[graph.V()];
        this.s = s;
        dfs(graph, s);
    }

    private void dfs(IGraph graph, int v) {
        marked[v] = true;
        for (int w : graph.adj(v)) {
            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(graph, w);
            }
        }
    }

    /**
     * 顶点v到 起点s是否存在路径
     *
     * @param v
     * @return
     */
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public int[] getEdgeTo() {
        return edgeTo;
    }

    /**
     * 打印顶点到 起点s的路径
     *
     * @param v
     */
    public void printPath(int v) {
        if (!hasPathTo(v)) {
            System.out.println(v + "到起点" + s + "不存在路径");
            return;
        }
        printEdgeTo(v);
    }

    /**
     * edgeTo[v]=w,  说明 w 是 v的前驱，即w->v
     * 通过递归，后续输出得到正向路径
     * @param v
     */
    private void printEdgeTo(int v) {
        if (v == s) {
            System.out.print(v);
            return;
        }
        printEdgeTo(edgeTo[v]);
        System.out.print("->" + v);
    }

}
